This invention relates generally to data processing systems and, more particularly, to a system for decoding and correcting errors in data using an error correction code.
Data stored on magnetic media, such as a magnetic disks, are typically stored in encoded form, so that errors in the stored data can possibly be corrected. The errors may occur, for example, because of inter-symbol interference, a defect in the disk, or noise. As the density of the data stored on the disk increases, more errors are likely, and the system is thus required to correct greater numbers of errors, which include greater numbers of burst errors. The speed with which the system corrects the errors is important to the overall speed with which the system processes the data.
Prior to recording, multiple-bit data symbols are encoded using an error correction code (ECC). When the data symbols are retrieved from the disk and demodulated, the ECC is employed to, as the name implies, correct the erroneous data.
Specifically, before a string of k data symbols is written to a disk, it is mathematically encoded using an (n, k) ECC to form n-k ECC symbols. The ECC symbols are then appended to the data string to form an n-symbol error correction code word, which is then written to, or stored, on the disk. When the data are read from the disk, the code words containing the data symbols and ECC symbols are retrieved and mathematically decoded. During decoding, errors in the data are detected and, if possible, corrected through manipulation of the ECC symbols [for a detailed description of decoding see, Peterson and Weldon, Error Correction Codes, 2nd Ed. MIT Press, 1972].
To correct multiple errors in strings of data symbols, the system typically uses an ECC that efficiently and effectively utilizes the various mathematical properties of sets of symbols known as Galois fields. Galois fields are represented xe2x80x9cGF (PM)xe2x80x9d, where xe2x80x9cPxe2x80x9d is a prime number and xe2x80x9cMxe2x80x9d can be thought of as the number of digits, base xe2x80x9cPxe2x80x9d, in each element or symbol in the field. P usually has the value 2 in digital computer and disk drive applications and, therefore, M is the number of bits in each symbol. The ECC""s commonly used with the Galois Fields are Reed Solomon codes or BCH codes.
There are essentially four major steps in decoding a corrupted code word of a high rate Reed-Solomon code or a BCH code. The system first determines error syndromes that are based on the results of a manipulation of the ECC symbols. Next, using the error syndromes, the system determines an error locator polynomial, which is a polynomial that has the same degree as the number of errors. The system then finds the roots of the error locator polynomial and from each root determines the location of an associated error in the code word. Finally, the system finds error values for the error locations.
The steps of determining the syndromes and finding the error locations are the most time consuming in the error correction process. This invention relates to the step of finding the error locations.
xe2x80x9cFastxe2x80x9d methods for finding four or fewer errors are known, and we have developed a system for finding 5 errors with the aid of a relatively small lookup table that is discussed in co-pending patent application IMPROVED FIVE-ERROR CORRECTION SYSTEM, Ser. No. 08/984,698 now U.S. Pat. No. 5,978,956. However, prior known systems that find the error locations for error locator polynomials of degree 6 or more perform time consuming Chien searches. A Chien search is a systematic trial and error approach that involves tying each element of the applicable Galois field as a root of the error locator equation. If the Galois Field is relatively large, the Chien search takes a long time, and thus, slows the error correction operation. An alternative to the Chien search is to use a lookup table that is entered with the 6 or more coefficients of the error locator polynomial. To correct even six errors, the associated lookup table is prohibitively large since it must include all possible distinct roots for the degree-six error locator polynomials. In GF(2M) the lookup table has (2M)6 entries. For systems that use 8-bit symbols, the lookup table has (28)6 or 248 entries, with each entry including six 8-bit roots of the error locator polynomial. For many systems, the lookup table takes up too much storage space. This is particularly true as larger Galois Fields are used to protect more data. Indeed, some systems may require that no lookup table is used.
An error correcting system for correcting xe2x80x9ctxe2x80x9d errors over GF(2m), where t is even and preferably greater than or equal to six, transforms the t-degree error locator polynomial into a polynomial in which atxe2x88x921xe2x89xa00, where ai is the coefficient of the xi term of the error locator polynomial. As necessary, the system further transforms the polynomial into one in which Tr(atxe2x88x921)xe2x89xa00, where Tr(ai) is the trace of ai or a mapping of ai to an element of GF(2). Based on the non-zero trace of atxe2x88x921, there are an odd number of roots that have traces equal to 1 and an odd number of roots that have traces equal to 0, since the sum of the roots of the polynomial is equal to atxe2x88x921 and the sum of the traces of the roots is equal to the trace of the sum.
The roots of the polynomial are elements of GF(2m), and all elements of GF(2m) with traces equal to 0 are roots of             S      ⁡              (        x        )              =                  ∑                  i          =          0                          m          -          1                    ⁢              x                  2          i                      ,
and all elements with traces equal to 1 are roots of S(x)+1. Accordingly, the polynomial can be factored into two factors, namely, one factor that is the greatest common divisor of the polynomial and S(x) and a second factor that is the greatest common divisor of the polynomial and S(x)+1. If the two factors each have degrees less than or equal four, the system uses a fast method to determine the roots of each of the factors. The system then, as necessary, transforms these roots into the roots of the error locator polynomial. Otherwise, the system continues factoring until the degrees of the factors are less than or equal to some desired degree before it determines the roots of the factors.
Preferably, the system determines the greatest common divisor of the polynomial and S(x) in two steps, first iteratively determining a residue R(x)xe2x89xa1S(x)mod t(x), where t(x) is the polynomial that has the term atxe2x88x921 with a trace of zero, and then calculating the greatest common divisor of t(x) and the lower-degree R(x). The system produces two factors of t(x), namely, g(x)=gcd(t(x), R(x)) and       h    ⁡          (      x      )        =                    t        ⁡                  (          x          )                            g        ⁡                  (          x          )                      .  
The system then determines the roots of the factors and transforms these roots into the roots of the error locator polynomial or, as necessary, continues factoring into factors of lower degree before determining the roots. We discuss the iterative technique for determining R(x) in more detail below.
When the degree of the error locator polynomial is odd, the system represents the roots ri of the error locator polynomial as a linear combination of ri,kxcex2k for k=0,1 . . . mxe2x88x921, where ri,kxcex5GF(2) and xcex2k is an element of a dual basis for GF(2m) over GF(2). Using the dual basis, Tr(xcex1jxcex2k)=1 when j=k and equals 0 otherwise. The roots ri are then
ri=ri,0xcex20+ri,1xcex21+ . . . +ri,mxe2x88x921xcex2mxe2x88x921
and       Tr    ⁡          (                        α          j                ⁢                  r          i                    )        =                    ∑                  k          =          0                          m          -          1                    ⁢                        r                      i            ,            k                          ⁢                  Tr          ⁡                      (                                          α                j                            ⁢                              β                k                                      )                                =          r              i        ,        j            
The system determines a value for j for which the traces of the roots are not all zero or all one. The greatest common divisor of the error locator polynomial and S(xcex1jx) then has a degree less than t, as does the greatest common divisor of the error locator polynomial and S(xcex1jx)+1. The system next determines the greatest common divisor of the polynomial and S(xcex1ix) by iteratively determining Rj(x)xe2x89xa1S(xcex1jx)mod c(x), where c(x) is the error locator polynomial, and then determining the greatest common divisor of c(x) and Rj(x). If the degree of Rjxe2x89xa71, the divisor is also a non-trivial factor of c(x). The system next determines two factors of c(x) as g(x)=gcd(c(x), Rj(x)) and       h    ⁡          (      x      )        =            t      ⁡              (        x        )                    g      ⁡              (        x        )            
and finds the roots as discussed above. We discuss the iterative technique for determining Rj(x) in more detail below.